\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{Garey1988}
\citation{ROE:8227001}
\citation{Brucker199977}
\citation{so30629}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{2}{section.1}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Problem definition and condition of optimality}{2}{section.2}}
\newlabel{sec:problemdefinition}{{2}{2}{Problem definition and condition of optimality}{section.2}{}}
\citation{Brucker19993}
\citation{Chretienne:2003:PSC:642013.642023}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Schedule optimality condition}{3}{subsection.2.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.1}General properties of a subgraph of $G$}{3}{subsubsection.2.1.1}}
\newlabel{def:shift}{{6}{3}{General properties of a subgraph of $G$}{definition.6}{}}
\newlabel{def:sigma_cost}{{7}{3}{General properties of a subgraph of $G$}{definition.7}{}}
\newlabel{def:late_early_etc}{{8}{3}{General properties of a subgraph of $G$}{definition.8}{}}
\newlabel{lemma:AETShift}{{1}{3}{General properties of a subgraph of $G$}{lemma.1}{}}
\citation{Chretienne:2003:PSC:642013.642023}
\newlabel{lemma:lateshift}{{2}{4}{General properties of a subgraph of $G$}{lemma.2}{}}
\newlabel{lemma:earlygraphs}{{3}{4}{General properties of a subgraph of $G$}{lemma.3}{}}
\newlabel{lemma:strictlyearlygraphs}{{4}{4}{General properties of a subgraph of $G$}{lemma.4}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.2}The equality graph and equality trees}{4}{subsubsection.2.1.2}}
\newlabel{sec:equalitygraphsandtrees}{{2.1.2}{4}{The equality graph and equality trees}{subsubsection.2.1.2}{}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.3}Schedule optimality condition}{5}{subsubsection.2.1.3}}
\newlabel{sec:scheduleoptimalitycondition}{{2.1.3}{5}{Schedule optimality condition}{subsubsection.2.1.3}{}}
\newlabel{lemma:EarlySubtree}{{5}{5}{Schedule optimality condition}{lemma.5}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Active equality tree from lemma \ref  {lemma:EarlySubtree}}}{5}{figure.1}}
\newlabel{fig:earlysubtree}{{1}{5}{Active equality tree from lemma \ref {lemma:EarlySubtree}}{figure.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Proof of lemma \ref  {lemma:EarlySubtree}}}{5}{figure.2}}
\newlabel{fig:earlysubtreeproof}{{2}{5}{Proof of lemma \ref {lemma:EarlySubtree}}{figure.2}{}}
\newlabel{def:predecessorssuccessors}{{14}{5}{Schedule optimality condition}{definition.14}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Splitting of an active equality tree}}{6}{figure.3}}
\newlabel{fig:roztrzeni}{{3}{6}{Splitting of an active equality tree}{figure.3}{}}
\newlabel{lemma:roztrzeni}{{6}{6}{Schedule optimality condition}{lemma.6}{}}
\newlabel{theorem:optimal}{{1}{6}{Schedule optimality condition}{theorem.2.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Algorithm}{6}{section.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Introduction}{6}{subsection.3.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Algorithm}{7}{subsection.3.2}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Inserting a new operation into $\mathcal  {S}^\sigma $}}{7}{algorithm.1}}
\newlabel{alg:insertoperation}{{1}{7}{Algorithm}{algorithm.1}{}}
\newlabel{alg:insertoperation:newopstart}{{3}{7}{Algorithm}{algorithm.1}{}}
\newlabel{alg:insertoperation:newopend}{{5}{7}{Algorithm}{algorithm.1}{}}
\newlabel{alg:insertoperation:maketreeontime}{{6}{7}{Algorithm}{algorithm.1}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces Insertion of a temporal constraint into $\mathcal  {S}^\sigma $}}{7}{algorithm.2}}
\newlabel{alg:insertTemporalConstraint}{{2}{7}{Algorithm}{algorithm.2}{}}
\newlabel{alg:insertTemporalConstraint:push}{{6}{7}{Algorithm}{algorithm.2}{}}
\newlabel{alg:insertTemporalConstraint:add}{{7}{7}{Algorithm}{algorithm.2}{}}
\newlabel{alg:insertTemporalConstraint:makeontime}{{8}{7}{Algorithm}{algorithm.2}{}}
\newlabel{alg:insertTemporalConstraint:activate}{{9}{7}{Algorithm}{algorithm.2}{}}
\newlabel{alg:insertTemporalConstraint:justadd}{{11}{7}{Algorithm}{algorithm.2}{}}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{dechtermeiripearl:ai:1991}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces Pushing of a tree to its optimum}}{8}{algorithm.3}}
\newlabel{alg:maketreeontime}{{3}{8}{Algorithm}{algorithm.3}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {4}{\ignorespaces Pushing of operation $i$ to a postition satisfying the given criteria}}{9}{algorithm.4}}
\newlabel{alg:push}{{4}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:difference}{{2}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:nodifference}{{8}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:getnearestevent}{{9}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:nearer}{{12}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:split}{{16}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:merge}{{18}{9}{Algorithm}{algorithm.4}{}}
\newlabel{alg:push:solustionexistencycheck}{{20}{9}{Algorithm}{algorithm.4}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {5}{\ignorespaces Splitting an equality tree at a given termporal constraint}}{9}{algorithm.5}}
\newlabel{alg:split}{{5}{9}{Algorithm}{algorithm.5}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {6}{\ignorespaces Merging two equality trees at a given termporal constraint}}{9}{algorithm.6}}
\newlabel{alg:merge}{{6}{9}{Algorithm}{algorithm.6}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {7}{\ignorespaces Finding the nearest event}}{9}{algorithm.7}}
\newlabel{alg:getnearestevent}{{7}{9}{Algorithm}{algorithm.7}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {8}{\ignorespaces Finding the nearest split event}}{9}{algorithm.8}}
\newlabel{alg:getnearestsplitevent}{{8}{9}{Algorithm}{algorithm.8}{}}
\newlabel{alg:getnearestsplitevent:branches1}{{5}{9}{Algorithm}{algorithm.8}{}}
\newlabel{alg:getnearestsplitevent:branches2}{{9}{9}{Algorithm}{algorithm.8}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {9}{\ignorespaces Finding the nearest split event in a subtree}}{10}{algorithm.9}}
\newlabel{alg:findnearestsplitevent}{{9}{10}{Algorithm}{algorithm.9}{}}
\newlabel{alg:findnearestsplitevent:costFn1}{{14}{10}{Algorithm}{algorithm.9}{}}
\newlabel{alg:findnearestsplitevent:costFn2}{{21}{10}{Algorithm}{algorithm.9}{}}
\newlabel{alg:findnearestsplitevent:costFn3}{{25}{10}{Algorithm}{algorithm.9}{}}
\newlabel{alg:findnearestsplitevent:nearest}{{30}{10}{Algorithm}{algorithm.9}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Correctness, finiteness and complexity of the algorithm}{10}{subsection.3.3}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.3.1}Correctness and finiteness of the algorithm}{10}{subsubsection.3.3.1}}
\newlabel{lemma:push}{{7}{10}{Correctness and finiteness of the algorithm}{lemma.7}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {10}{\ignorespaces Finding the nearest merge event}}{10}{algorithm.10}}
\newlabel{alg:getnearestmergeevent}{{10}{10}{Algorithm}{algorithm.10}{}}
\newlabel{alg:getnearestmergeevent:foreachk}{{7}{10}{Algorithm}{algorithm.10}{}}
\newlabel{alg:getnearestmergeevent:foreachkl}{{8}{10}{Algorithm}{algorithm.10}{}}
\newlabel{alg:getnearestmergeevent:mergetime}{{10}{10}{Algorithm}{algorithm.10}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {11}{\ignorespaces Splitting on-time weakly active equality tree into on-time active equality trees}}{10}{algorithm.11}}
\newlabel{alg:activate}{{11}{10}{Algorithm}{algorithm.11}{}}
\citation{Press:2007:NRE:1403886}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {3.3.2}Complexity of the algorithm}{11}{subsubsection.3.3.2}}
\citation{Chretienne:2003:PSC:642013.642023}
\citation{Chretienne:2003:PSC:642013.642023}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Source code}{12}{subsection.3.4}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Conclusions}{12}{section.4}}
\@writefile{toc}{\contentsline {section}{\numberline {A}Appendix}{12}{appendix.A}}
\newlabel{sec:appendix}{{A}{12}{Appendix}{appendix.A}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.1}Example of \textsc  {insertTemporalConstraint}()}{12}{subsection.A.1}}
\newlabel{sec:example}{{A.1}{12}{Example of \textsc {insertTemporalConstraint}()}{subsection.A.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {A.2}Counterexample of why a weakly active equality tree does not guarantee optimality}{12}{subsection.A.2}}
\newlabel{sec:counterexample}{{A.2}{12}{Counterexample of why a weakly active equality tree does not guarantee optimality}{subsection.A.2}{}}
\bibstyle{abbrvnat}
\bibdata{bibliography}
\bibcite{Brucker19993}{{1}{1999{a}}{{Brucker et~al.}}{{Brucker, Drexl, M\IeC {\"o}hring, Neumann, and Pesch}}}
\bibcite{Brucker199977}{{2}{1999{b}}{{Brucker et~al.}}{{Brucker, Hilbig, and Hurink}}}
\bibcite{Chretienne:2003:PSC:642013.642023}{{3}{2003}{{Chr{\'e}tienne and Sourd}}{{}}}
\bibcite{ROE:8227001}{{4}{2001}{{Chr\IeC {\'e}tienne}}{{}}}
\bibcite{dechtermeiripearl:ai:1991}{{5}{1991}{{Dechter et~al.}}{{Dechter, Meiri, and Pearl}}}
\bibcite{so30629}{{6}{1998}{{{Hurink} and {Keuchel}}}{{}}}
\bibcite{Garey1988}{{7}{1988}{{Michael R.~Garey}}{{}}}
\bibcite{Press:2007:NRE:1403886}{{8}{2007}{{Press et~al.}}{{Press, Teukolsky, Vetterling, and Flannery}}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Example}}{13}{figure.4}}
\newlabel{fig:example}{{4}{13}{Example}{figure.4}{}}
\newlabel{fig:example:first}{{4(a)}{13}{Subfigure 4(a)}{subfigure.4.1}{}}
\newlabel{sub@fig:example:first}{{(a)}{13}{Subfigure 4(a)\relax }{subfigure.4.1}{}}
\newlabel{fig:example:second}{{4(b)}{13}{Subfigure 4(b)}{subfigure.4.2}{}}
\newlabel{sub@fig:example:second}{{(b)}{13}{Subfigure 4(b)\relax }{subfigure.4.2}{}}
\newlabel{fig:example:third}{{4(c)}{13}{Subfigure 4(c)}{subfigure.4.3}{}}
\newlabel{sub@fig:example:third}{{(c)}{13}{Subfigure 4(c)\relax }{subfigure.4.3}{}}
\newlabel{fig:example:fourth}{{4(d)}{13}{Subfigure 4(d)}{subfigure.4.4}{}}
\newlabel{sub@fig:example:fourth}{{(d)}{13}{Subfigure 4(d)\relax }{subfigure.4.4}{}}
\newlabel{fig:example:fifth}{{4(e)}{13}{Subfigure 4(e)}{subfigure.4.5}{}}
\newlabel{sub@fig:example:fifth}{{(e)}{13}{Subfigure 4(e)\relax }{subfigure.4.5}{}}
\newlabel{fig:example:sixth}{{4(f)}{13}{Subfigure 4(f)}{subfigure.4.6}{}}
\newlabel{sub@fig:example:sixth}{{(f)}{13}{Subfigure 4(f)\relax }{subfigure.4.6}{}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Step 0}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Step 1}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Step 2}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Step 3}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(e)}{\ignorespaces {Step 4}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(f)}{\ignorespaces {Step 5, 6 and 7}}}{13}{subfigure.4.6}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Problematic operations structure}}{13}{figure.5}}
\newlabel{fig:aktivityVM}{{5}{13}{Problematic operations structure}{figure.5}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Cost functions in problematic operations structure}}{13}{figure.6}}
\newlabel{fig:costfunctionsVM}{{6}{13}{Cost functions in problematic operations structure}{figure.6}{}}
\newlabel{eqnarr:G1}{{1}{14}{Acknowledgements}{equation.A.1}{}}
\newlabel{eqnarr:G2}{{2}{14}{Acknowledgements}{equation.A.1}{}}
\newlabel{eqnarr:G12}{{3}{14}{Acknowledgements}{equation.A.1}{}}
\newlabel{item:a}{{1}{14}{Acknowledgements}{Item.1}{}}
\newlabel{item:b}{{2}{14}{Acknowledgements}{Item.2}{}}
\newlabel{item:c}{{3}{14}{Acknowledgements}{Item.3}{}}
